package cn.orange.ch03_linked;

/**
 * LC707.设计链表
 * 设计并实现自己的链表
 */
public class MyLinkedList {
    private Node head;
    private int size;
    public MyLinkedList() {
        this.head = new Node(-1);
        this.size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        Node curr = head;
        for (int i = -1; i < index; i++) {
            curr = curr.next;
        }
        return curr.val;
    }

    public void addAtHead(int val) {
        head.next = new Node(val, head.next);
        this.size++;
    }

    public void addAtTail(int val) {
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = new Node(val);
        this.size++;
    }

    public void addAtIndex(int index, int val) {
        if (index >= 0 && index <= size) {
            Node prev = head;
            for (int i = -1; i < index - 1; i++) {
                prev = prev.next;
            }
            prev.next = new Node(val, prev.next);
            this.size++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            Node prev = head;
            for (int i = -1; i < index - 1; i++) {
                prev = prev.next;
            }
            if (prev.next != null) {
                prev.next = prev.next.next;
            }
            this.size--;
        }
    }

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }
}
